Особливості та додаткові можливості застосування методу карт Карно. Карти Карно (їх різновидом є карти Вейча, які будуються як розгортки куба на площині), є графічним представленням таблиць істинності. Тому вони будуються або по таблиці істинності аналізованої функції, чи ж по її СНДФ. Нагадаємо, що кожен рядок таблиці істинності, для якої функція рівна одиниці, відповідає конкретному мінтерму функції, представленій в СНДФ. Рядок, для якого функція рівна нулю є визначеним макстермом функції, представленій в СНКФ. Карта Карно є прямокутником, розбитим на квадрати, число яких рівне загальному числу наборів для даної функції n змінних, тобто воно рівне 2n. Так, для функції чотирьох змінних квадратів буде 16, для п'яти змінних - 32 і т.д. Кожен квадрат відповідає певному набору або терму, причому набори розташовуються так, щоб сусідні набори або терми, як по горизонталі, так і по вертикалі, відрізнялися б тільки значенням однієї змінної: у одному квадраті вона з інверсією, а в другом, сусідньому - без. Функцію в СНДФ наносять на карту, відзначаючи, наприклад, знаком 1 квадрати, відповідні тим наборам, на яких функція рівна одиниці, тобто в СНДФ функції відповідний мінтерм. Решта квадратів наголошується знаком 0. Іноді в кутку квадрата ставлять номер набору. Такий спосіб використовується, якщо функція задана числовим чином, але він неудо-бен для процедури мінімізації. Логічна функція двох змінних, де а) - таблиця істинності; а б) - карта Карно. У результаті карту Карно можна оформляти будь-яким відповідним чином, але тільки так, щоб кожен квадрат відповідав певному набору або терму і вони, як вже наголошувалося, розташовувалися б так, щоб сусідні набори або терми, як по горизонталі, так і по вертикалі, відрізнялися б тільки значенням однієї змінної: у одному квадраті вона з інверсією, а в другом, сусідньому - без. Причому, треба врахувати, що квадрати, розташовані на протівополжних кінцях кожного рядка або стовпця, також є сусідніми. Перерахуємо послідовність дій, що виконуються для мінімізації функції по методу Карно. (1) Початкова функція, що підлягає мінімізації, повинна бути представлена в НДФ. Потім її треба представити в СНДФ. Чи ж складається таблиця істинності функції, що мінімізується. Як вже наголошувалося, між рядками таблиці істинності і клітками (осередками) на карті Карно існує взаємно однозначна відповідність. Коли карта Карно складається по СНДФ функції, що мінімізується, то очевидно, що кожна змінна без заперечення замінюється її значенням 1, а із запереченням - 0. (2) Потім будується карта Карно за принципом, описаним раніше. Представимо систему координат, в якій, наприклад, для функції двох аргументів по горизонтальній осі відкладаються значення одного аргументу, а по вертикалі - іншого. На перетині відповідних координат одержуємо осередок, куди записується значення функції (0 або 1), відповідне даному набору. Якщо функція представлена в СНДФ, то в осередку відповідної що існує мінтерму записується 1, а в осередку неіснуючого мінтерма - 0. (3) Після цього об'єднуються в групи суміжні осередки, в яких записані одиниці, таким чином: об'єднується обов'язково парна кількість сусідніх осередків з одиницями як по вертикалі, так і по горизонталі. Причому, кожен осередок з 1 може потрапити одночасно в дві групи, одержані в результаті об'єднання одиниць як по вертикалі, так і по горизонталі. (4) Кожній такій групі ставиться у відповідність новий мінтерм для зображення початкової функції у формі мінімальної НДФ. (5) Зображення кожного нового мінтерма формується по наступному алгоритму: а) змінна, яка в кожному осередку освіченої групи має значення тільки 0, зображається її інверсією; б) змінна, яка в кожному осередку групи має значення тільки 1, зображається без інверсії; в) змінна, яка в межах освіченої групи міняє своє значення, не зображається, тобто відкидається. Таким чином, карту Карно можна розглядати як графічне представлення сукупності всіх (сушествующих і що не існують) мінтермов функц...